package leetcode_2401_2500;

public class LeeCode_2470 {
    public static void main(String[] args) {
        System.out.println(subarrayLCM(new int[]{3, 6, 2, 7, 1}, 6));
//        System.out.println(subarrayLCM(new int[]{3}, 2));
//        System.out.println(subarrayLCM(new int[]{1}, 1));
        System.out.println(subarrayLCM(new int[]{2,1,1,5}, 5));
    }

    private static int subarrayLCM(int[] nums, int k) {
        int n = nums.length, ans = 0;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            for (int j = i; j < n; j++) {
                x = lcm(x, nums[j]);
                if (x == k){
                    ans++;
                }else if (x > k)
                    break;
            }
        }
        return ans;
    }

    private static int lcm(int x, int y){
        return x * y / (gcd(x, y));
    }

    private static int gcd(int x, int y) {
        while (x != 0) {
            int tmp = x;
            x = y % x;
            y = tmp;
        }
        return y;
    }
}
